<html>
<head><meta charset="utf-8"><title>Interned sequences are expensive · wg-traits · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/index.html">wg-traits</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html">Interned sequences are expensive</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="212617399"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212617399" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nathan Whitaker <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212617399">(Oct 07 2020 at 20:51)</a>:</h4>
<p>I was looking into chalk's performance in r-a and I noticed that we spend a <em>lot</em> of time interning sequences (particularly <code>Substitution</code>s). For perspective, we seem to spend anywhere from 1/6 to &gt;1/2 of the solving time just interning <code>Substitution</code>s. In some cases we call <code>intern_substitution</code> (which on the r-a side basically <code>collect</code>s into a <code>Vec</code>) almost 600,000 times in the course of solving a single (top-level) goal.</p>



<a name="212617644"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212617644" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nathan Whitaker <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212617644">(Oct 07 2020 at 20:53)</a>:</h4>
<p>I suspect a good amount of this comes from <code>fold</code>ing sequences, as each fold call has at least 1 call to the interner just to construct the new sequence.</p>



<a name="212617760"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212617760" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Nathan Whitaker <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212617760">(Oct 07 2020 at 20:54)</a>:</h4>
<p>I'm not sure how actionable this is, if at all, but it seems like we might be able to do better here</p>



<a name="212620128"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212620128" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212620128">(Oct 07 2020 at 21:13)</a>:</h4>
<p><em>rustc tries to reuse previous interned values while folding by using <code>if self.kind == kind { self } else { tcx.mk_ty(kind) }</code> or something like this...</em></p>
<p>Are you already doing this is chalk?</p>



<a name="212626216"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212626216" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212626216">(Oct 07 2020 at 22:18)</a>:</h4>
<p>Hmm, yeah, that sounds like a problem</p>



<a name="212626224"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212626224" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jack Huey <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212626224">(Oct 07 2020 at 22:18)</a>:</h4>
<p><span class="user-mention" data-user-id="216206">@lcnr</span> no we don't</p>



<a name="212654815"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/212654815" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#212654815">(Oct 08 2020 at 07:26)</a>:</h4>
<p>might be really beneficial to try this then <span aria-label="laughing" class="emoji emoji-1f606" role="img" title="laughing">:laughing:</span> iirc adding that change to <code>Predicate</code>s improved perf by 2%</p>



<a name="213971199"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/144729-wg-traits/topic/Interned%20sequences%20are%20expensive/near/213971199" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/144729-wg-traits/topic/Interned.20sequences.20are.20expensive.html#213971199">(Oct 20 2020 at 19:53)</a>:</h4>
<p>Yeah, I was thinking that we needed some helper methods on the <code>Interner</code> trait for this sort of thing</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>